\subsection{Arbre Binaire de Décision}
\paragraph{} L'objectif de l'arbre binaire de décision, est de pouvoir se localiser rapidement, de préférence en temps réel sur la carte. Au lieu de comparer notre position à celle de tous les éléments composant la carte, nous allons suivre un ensemble de décisions (gauche ou droite) et ainsi arriver dans la zone où se trouve la position recherchée.

\paragraph{}
Pour mettre en œuvre cette idée, nous avons décidé d'implémenter l'algorithme présenté dans le cours par M. Jean-Michel Couvreur, l'algorithme des verticales. Afin de se simplifier la vie, nous allons travailler sur deux arbres différents, un pour tous les polygones du campus (différents UFRs, forêts, restaurants, etc...) et un pour toutes les routes et les chemins parcourant le campus. Ainsi pour savoir où nous sommes nous allons tout d'abord chercher à savoir si nous sommes sur une route ou un chemin à l'aide de l'arbre de décision des chemins, puis si nous ne sommes pas sur un chemin, nous chercherons dans le second arbre qui lui concerne les polygones (informations moins précises).

\paragraph{}
Pour se faire, nous passons par plusieurs étapes que nous allons détailler.
\subsubsection{Récupérer la carte}
\paragraph{}
Tout d'abord, il nous est impossible d'exploiter directement les informations disponibles dans la base de données, nous avons donc mis en place un ensemble de pré-traitements permettant de rendre exploitables les données présentes dans notre carte.

\paragraph{}
Nous utiliserons les méthodes mises en place dans la partie \textbf{Données géographiques} pour récupérer dans des listes, d'un coté tous les polygones qui composent la carte, et de l'autre, l'ensemble des routes et chemins quadrillant l'université.

\paragraph{}
Dans l'algorithme présenté en cours, l'arbre binaire créé des verticales sur tous les points présents dans l'espace étudié. Nous avons donc recours à plusieurs méthodes pour transformer un ensemble de polygones en ensemble de segments (nous découpons simplement le polygone) et un ensemble de chemins en ensemble de segments (nous récupérons tous les chemins, les transformons en polygones pour pouvoir savoir si nous sommes sur le chemin ou à coté, puis nous redécoupons les polygones ainsi créés).

\subsubsection{Assigner les zones adjacentes aux segments}
\paragraph{}
Pour bien se localiser, il est nécessaire de savoir ce qui se trouve de chaque coté de chaque segment composant l'espace étudié. Pour cela, tout segment doit connaître la zone qui est à sa gauche (ou en dessous de lui) et celle à sa droite(ou au dessus). Afin d'affecter celles-ci, nous avons procédé de la manière suivante. 

\paragraph{}
Dans un premier temps nous savons que tous les polyèdres sont décrits dans le sens trigonométrique, et donc par conséquent, qu'à partir d'un produit vectoriel, le polygone est toujours du \textit{même coté} du segment. En effet, en partant du début du segment, c’est toujours en tournant dans le sens trigonométrique que nous allons vers \textit{le centre (ou l'intérieur)} du polygone. 
\begin{center}
\includegraphics[scale=0.5]{../images/centrepolygone.png}
\end{center}
la figure précédente illustre de quel \textit{coté} se trouve le polygone par rapport au segment. Nous affectons donc pour chaque segment du polygone en zone de gauche le \textit{polygone} et de droite: \textit{l'extérieur}.
\newpage
\subsubsection{Éclater les polygones (bâtiments ou chemins) en segments}
\paragraph{}
Pour que l'algorithme fonctionne, il faut savoir pour chaque polygone, si le point recherché appartient au polygone ou non. Pour cela, nous créons des polygones pour tous les chemins (comme cela nous considérons des routes qui sont \textit{épaisses} au lieu de simple lignes). Avec cette étape, que l'on soit sur une route ou dans un bâtiment ou même une foret, nous sommes toujours dans un polygone. La figure suivante va vous montrer les deux étapes dont ce paragraphe parle : 
\begin{center}
\includegraphics[scale=0.3]{../images/eclatement.png}
\end{center}
Ensuite nous passons tous les polygones dans le découpage pour ne garder que des segments qui connaissent leurs zones adjacentes.

\subsection{Ajout de verticales}
\paragraph{}
Nous en avons terminé avec les pré-traitements et nous sommes en présence d'un ensemble de segments qui décrit notre campus, ces segments étant conscients de leurs zones adjacentes. Nous pouvons donc attaquer l'algorithme présenté par M. Couvreur.

\paragraph{}
L'algorithme cherche à découper l'espace en \textit{tranches} verticales afin que dans les premiers \textit{étages} de l'arbre nous soyons capable de savoir rapidement dans quelle \textit{tranche} de la carte nous nous situons. Pour cela nous prenons donc un ensemble de segments et nous ajoutons dans un liste tous les points distincts de cet ensemble de segments :
\begin{verbatim}
For(Segment s : les segments){
	if(!dejaPresent(s.getDebut,TouslesPoints)){
		ajouter(s.getDebut,TouslesPoints);
		}
		//idem pour le point de fin du segment
}
\end{verbatim}
Ensuite, pour tous ces points nous créons une verticale d’abscisse : point.getX(), et nous avons toutes nos verticales. 
\begin{center}
\includegraphics[scale=0.5]{../images/tranches.png}
\end{center}
On peut voir sur la figure précédente comment l'algorithme découpe la carte (ici constituée d'un seul polygone pour l'exemple) en \textit{tranches}.
\newpage
\subsubsection{Calcul de segments intersectant la tranche}
\paragraph{}
De la meme manière que nous avons découpé verticalement notre carte à l'aide de verticale, nous allons découpé chaque \textit{tranche} à l'aide des segments intersectants celle-ci. en effet, pour chaque segment traversant notre verticale et une autre verticale (la suivante ou la précédente suivante la direction) nous allons créer des nœuds fils qui contiendrons les segments.

\paragraph{}
Dans un premier temps, nous calculons tous les segments qui apparaissent dans la tranche : la figure suivante montre les trois cas qui se présentent : 
\begin{center}
\includegraphics[scale=0.5]{../images/troiscas.png}
\end{center}
Pour résumer, un segment doit être pris en compte si et seulement si il n’est ni tout à droite de la verticale de droite, ni tout à gauche de la verticale de gauche. On obtient donc pour chaque \textit{tranche} une liste de segments \textit{intersections} de cette tranche. Si on se reporte à la figure de la page précédente sur les tranches, on constate que \textbf{s1} est dans le cas deux de la figure précédente alors que \textbf{s5} est dans le cas trois.

\subsubsection{Calcul de zones contenues entre chaque segments}
\paragraph{}
Comme évoqué précédemment, pour pouvoir se localiser il faut savoir ou nous nous trouvons, et lorsque nous arrivons à cette étape, nous savons que nous sommes autour de segments connus, il ne reste plus qu'à nous situer par rapport à ces segments, c'est a dire, créer pour chaque segment, des noeuds fils pour indiquer ce qui se trouve à leur gauche et à leur droite. Dans les faits, dire quelle zone se trouve au dessus du segment et laquelle se situe en dessous. Nous n'allons pas paraphraser ce qui a été précédemment expliqué, mais grâce à l'affectation de zone dans les prétraitements, il nous reste a mettre en fils gauche la zone basse, et en fils droit la zone haute.
\begin{center}
\includegraphics[scale=0.5]{../images/zone.png}
\newpage
\end{center}
\subsubsection{Aperçu de l'arbre}
\paragraph{}
Afin de pouvoir mettre un schéma sur les explications précédentes, nous allons maintenant présenter plusieurs figures qui vont mettre en lumière le contenu de l'arbre binaire à différent niveaux.

\paragraph{}
Pour commencer voici un aperçu non-exhaustif de ce que contient l'arbre à différents niveaux : 
\begin{center}
\includegraphics[scale=0.5]{../images/niveaux.png}
\end{center}

\newpage
\paragraph{}
Et pour mieux se rendre compte de ce que nous donne l'arbre nous allons montrer ce que voit dans ces fils, une verticale et un segment : 
\begin{center}
\includegraphics[scale=0.5]{../images/POVverticale.png}
\end{center}
\begin{center}
\includegraphics[scale=0.5]{../images/POVsegment.png}
\end{center}

\subsubsection{Efficacité}
\paragraph{}
Nous l'avons évoqué, cet alogrithme est plus efficace que de comparer la position souhaitée à tous les éléments qui composent la carte, toutefois, notre implémentation est particulièrement efficace à la recherche car nous avons été malin lors de la construction de l'arbre.

\paragraph{}
En effet lors de découpage, il est possible de suivre deux approches, linéaire ou dichotomique. La première considère que l'on ai soit à gauche du premier séparateur (verticale ou segment) soit à droite du suivant, soit à droite du dernier. Alors que la dichotomie nous donne, suis-je dans la partie gauche ou droite de la carte, et dans cette partie-ci suis-je à gauche ou à droite, et ainsi de suite réduisant l'espace à analyser de moitié par itération, et ce dans le sens vertical ou horizontal. 

\paragraph{}
Nous avons donc suivi la seconde approche, qui consiste à placer comme nœud père, le séparateur médian de l'espace analysé, et en fils de celui ci, les séparateur restants, en reprenant le même principe pour les fils,à gauche comme à droite. Un exemple sera sans doute plus parlant :
\begin{center}
\includegraphics[scale=0.5]{../images/dichotomietranches.png}
\end{center} 

\paragraph{}
Dans la figure précédente, on put se rendre compte du gain de temps si nous cherchons un point qui se trouve dans la zone \textbf{z5} , dans le cas linéaire, nous sommes obligé de parcourir toutes les tranches précédentes et donc mettre 6 étapes pour trouver la \textbf{z5}. alors que dans le cas dichotomique, il me faut que 3 itérations pour trouver. Pour informations, l'arbre des chemins du campus compte une peu plus de 466000 nœuds, et nous sommes content de ne pas avoir à attendre 465999 étapes pour savoir que nous sommes dans la dernière zone.

\paragraph{}
C'est donc au prix des gros efforts de programmation que nous obtenons un arbre de décision, presque équilibré, mais qui permet une recherche dichotomique sur la carte du campus, ce qui permet une localisation rapide d'un point sur la carte.